#include <stdio.h>
#include <stdlib.h>

// 链表节点结构定义
typedef struct ListNode {
    int data;
    struct ListNode * next;
} ListNode;

// 反转链表部分函数
ListNode * reverseList(ListNode * head) {
    ListNode * prev = NULL;
    ListNode * curr = head;
    ListNode * next = NULL;
    
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 倒置从第i个结点到第m个结点的函数（修复版本）
void reversePartialList(ListNode * L, int i, int m) {
    if (L == NULL || i <= 1 || i > m) return;
    ListNode * curr = L;
    ListNode * prevNode = NULL;
    // 找到第i-1个结点
    for (int j = 1; j < i; j++) {
        prevNode = curr;
        curr = curr->next;
        if (curr == NULL) return;
    }
    // curr现在指向第i个节点
    ListNode * startNode = curr;  // 保存第i个节点
    // 找到第m个结点，同时记录原始的循环连接
    ListNode * endNode = curr;
    for (int j = i; j < m; j++) {
        endNode = endNode->next;
        if (endNode == NULL) return;
    }
    // 保存第m个节点原本指向的节点（可能是第i个节点，形成循环）
    ListNode * originalNext = endNode->next;
    // 临时断开第m个节点的连接，以便反转
    endNode->next = NULL;
    // 反转第i到第m个节点的子链表
    ListNode * newHead = reverseList(startNode);
    // 重新连接：
    // 1. 第i-1个节点连接到新的头部（原第m个节点）
    if (prevNode != NULL) {
        prevNode->next = newHead;
    }
    // 2. 新的尾部（原第i个节点）连接到原来第m个节点指向的节点
    startNode->next = originalNext;
}

// 创建链表节点
ListNode * createNode(int data) {
    ListNode * node = (ListNode *)malloc(sizeof(ListNode));
    node->data = data;
    node->next = NULL;
    return node;
}

// 从数组创建链表
ListNode * createListFromArray(int arr[], int size) {
    if (size <= 0) return NULL;
    
    ListNode * head = createNode(arr[0]);
    ListNode * curr = head;
    
    for (int i = 1; i < size; i++) {
        curr->next = createNode(arr[i]);
        curr = curr->next;
    }
    return head;
}

// 创建部分循环链表的函数
ListNode * createPartialCyclicList(int arr[], int size, int cycleStart, int cycleEnd) {
    if (size <= 0 || cycleStart < 1 || cycleEnd > size || cycleStart > cycleEnd) {
        return NULL;
    }
    
    ListNode * head = createNode(arr[0]);
    ListNode * curr = head;
    ListNode * cycleStartNode = NULL;
    ListNode * cycleEndNode = NULL;
    
    // 创建链表并记录循环起始和结束节点
    for (int i = 1; i < size; i++) {
        curr->next = createNode(arr[i]);
        curr = curr->next;
        
        if (i + 1 == cycleStart) {  // 第i个节点（从1开始计数）
            cycleStartNode = curr;
        }
        if (i + 1 == cycleEnd) {
            cycleEndNode = curr;
        }
    }
    
    // 如果第1个节点是循环起始点
    if (cycleStart == 1) {
        cycleStartNode = head;
    }
    // 创建部分循环：第cycleEnd个节点指向第cycleStart个节点
    if (cycleStartNode && cycleEndNode) {
        cycleEndNode->next = cycleStartNode;
    }
    return head;
}

// 安全打印链表（防止无限循环）
void printListSafe(ListNode * head, int maxPrint) {
    ListNode * curr = head;
    int count = 0;
    
    while (curr != NULL && count < maxPrint) {
        printf("%d ", curr->data);
        curr = curr->next;
        count++;
    }
    if (count == maxPrint) {
        printf("... (链表可能有循环，已限制打印)");
    }
    printf("\n");
}

// 测试
int main() {
    
    printf("\n=== 测试1: 部分循环链表的反转 ===\n");
    int arr2[] = {1, 2, 3, 4, 5, 6, 7, 8};
    ListNode * list2 = createPartialCyclicList(arr2, 8, 3, 6);  // 第6个节点指向第3个节点形成循环
    printf("原部分循环链表（限制打印20个元素）: ");
    printListSafe(list2, 20);
    
    printf("反转循环部分（第3-6个结点）...\n");
    reversePartialList(list2, 3, 6);
    printf("反转后的链表: ");
    printListSafe(list2, 20);
    
    printf("\n=== 测试2: 另一个部分循环链表 ===\n");
    int arr3[] = {10, 20, 30, 40, 50, 60, 70, 80};
    ListNode * list3 = createPartialCyclicList(arr3, 8, 2, 5);  // 第5个节点指向第2个节点
    printf("原部分循环链表: ");
    printListSafe(list3, 15);
    
    reversePartialList(list3, 2, 5);
    printf("反转第2-5个结点后: ");
    printListSafe(list3, 15);
    
    // 注意：由于有循环结构，不能简单使用freeList
    // 在实际应用中需要特殊的内存释放策略
    printf("\n注意：循环链表的内存释放需要特殊处理\n");
    
    return 0;
}